/**
 * 1370. 上升下降字符串
 * https://leetcode-cn.com/problems/increasing-decreasing-string/
 */
public class Solutions_1370 {
    public static void main(String[] args) {
        String s = "aaaabbbbcccc";  // output: "abccbaabccba"
//        String s = "rat";  // output: "art"
//        String s = "leetcode";  // output: "cdelotee"
//        String s = "ggggggg";  // output: "ggggggg"
//        String s = "spo";  // output: "ops"

        String result = sortString(s);
        System.out.println(result);
    }

    public static String sortString(String s) {
        if (s == null) {
            return "";
        }
        char[] arr = s.toCharArray();
        // map[0] = 5，表示字符 'a' 在字符串 s 中出现了 5 次
        int[] map = new int[26];
        char[] res = new char[arr.length];
        int idx = 0;
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            map[arr[i] - 'a'] ++;
        }
        // 循环，直到 idx == len，即字符串 s 中的全部字符都添加到了 res 中
        while (idx < len) {
            // 正向遍历一遍字符，字符是从小到大
            for (int i = 0; i < map.length; i++) {
                if (map[i] > 0) {
                    // 添加字符到结果数组；出现次数减 1
                    res[idx++] = (char) (i + 'a');
                    map[i] --;
                }
            }
            // 反向遍历一遍字符，字符是从大到小
            for (int i = map.length - 1; i >= 0 && idx < len; i--) {
                if (map[i] > 0) {
                    res[idx++] = (char) (i + 'a');
                    map[i] --;
                }
            }
        }
        return String.valueOf(res);
    }
}
